## Fast computation of cyclotomic polynomials


from PyM import *


def fast_cyclotomic(n,x='x'):
    if n==0: return 1
    F = ifactor(n)
    P = list(F.keys())
    m = p = P[0]
    [_,x] = polynomial_ring(Z_,x)
    f = sum([x**j for j in range(p)])
    for p in P[1:]:
        m *= p
        f = evaluate(f,x**p)/f
    return evaluate(f,x**(n//m))
    

show(fast_cyclotomic(factorial(6),'T'))

show(fast_cyclotomic(1000,'T'))